#include <cstdlib>
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;

#define INF 100000

/*-- INICIO DECLARACION DE CLASES --*/

class intNode;
class intList;
class intQueue;
class dijkstraNode;
class dijkstraList;
class streetNode;
class streetList;
class Stack;
class streetCars;
class carqueueNode;
class carqueueList;
class carqueueQueue;
class Edge;
class Vertex;
class Graph;

/*-- FIN DECLARACION DE CLASES --*/

/* Estructura de nodos que guardan datos enteros */
class intNode{
    private: 
        int data;
        intNode *next;
    public:
        intNode() {next=NULL;}; //Constructor de nodos sin datos
        intNode(int a) {data=a; next=NULL;}; //Constructor de nodos con datos
        void set_data(int a) {data=a;}; //Cambio el dato del nodo
        void set_next(intNode *n) {next=n;}; //Asigno puntero hacia el proximo nodo
        int get_data() {return data;}; //Devuelve el valor del dato del nodo
        intNode *get_next() {return next;}; //Devuelve el valor del puntero del siguiente nodo
        bool checkempty() {return next==NULL;}; //Devuelve si el nodo no tiene datos
};

/* Lista compuesta de nodos enteros */
class intList{
    private: 
		intNode *start;
    public:
        intList() {start=new intNode();}; //Creo una lista vacio
        intList(intNode *n) {start=n;}; //Creo una lista con un nodo vacio
        void add(int d) {intNode *newNode=new intNode(d); newNode->set_next(start); start=newNode;}; //Agrego un nodo a la lista
        bool checkempty(void) {return start->checkempty();}; //Devuelve si la lista es vacia
        int head(void) {if(!checkempty()) return start->get_data();}; //Devuelve la cabeza de lista si no es vacia
        intList *remain(void) {intList *l=new intList(start->get_next());return (l);}; //Devuelve una lista sin la cabeza
        intNode *intList_getstart() {return start;}; //Devuelve el nodo inicial
};

/* Cola FIFO compuesta de nodos enteros */
class intQueue{
    private:
        intList *l;
        intNode *startq;
        void update_start(intList *l,intNode *p){ //Cambio el nodo inicio
			if (l->checkempty())  //Si la lista es vacia el nodo inicial es el que viene en la funcion
				startq=p;
			else //Si no es vacia recursivamente se va pasando por todos los nodos hasta llegar al principio
				this->update_start(l->remain(),l->intList_getstart());
		};
        void dounqueue(intNode *p,intNode *s){ //Desencolar
			if (p->get_next()==NULL){ //Si el nodo p no tiene otro nodo detras inmediato
				if (s!=NULL){ 
					s->set_next(NULL);
				}
			delete(p); //Desencolo p
			}
			else //En caso de que si tenga recursivamente le paso el nodo proximo a p ademas de p
				this->dounqueue(p->get_next(),p);
		};
    public:
		intQueue(void) {l=new intList();update_start(l,NULL);}; //Constructor de la cola
		~intQueue(void) {delete(l);}; //Destructor de la cola
		int emptyqueue() {return l->checkempty();}; //Chequea si la lista correspondiente esta vacia
		int top() {if (!emptyqueue()) return startq->get_data();}; //Devuelve el tope de la lista si no es vacia
		void _queue(int a) {l->add(a); if (startq==NULL) update_start(l,startq);}; //Encola nodos en la lista
		void _unqueue() {if (!emptyqueue()){dounqueue(l->intList_getstart(),NULL); update_start(l,NULL);}}; //Desencola los nodos de la lista
};

/* Estructura de nodos para uso en Dijkstra */
class dijkstraNode{
    private: 
        int data;
        int span;
        bool seen;
        intQueue *q;
        dijkstraNode *next;
    public:
        dijkstraNode() {next=NULL;}; //Nodo vacio
        dijkstraNode(int a) {data=a; q=new intQueue(); next=NULL;};
        void set_data(int a) {data=a;};
        void set_next(dijkstraNode *n) {next=n;};
        int get_data() {return data;};
        dijkstraNode *get_next() {return next;};
        bool checkempty() {return next==NULL;};
        void set_span(int d) {span=d;}; //Set de la distancia
        int get_span() {return span;}; //Devuelve la distancia
        void set_seen(bool v) {seen=v;}; //Set si el nodo ya fue visto
        bool get_seen() {return seen;}; //Devuelve si el nodo fue visto
        void set_intQueue(intQueue *c) {q = c;}; //Set de cola al nodo
        intQueue *get_intQueue() {return q;}; //Devuelve la cola del nodo
};

/* Lista de Dijkstra, representa un conjunto de los vertices */
class dijkstraList{
    private: 
		dijkstraNode *start;
    public:
        dijkstraList() {start=new dijkstraNode();};
        dijkstraList(dijkstraNode *n) {start=n;};
        void add(int d) {dijkstraNode *newNode=new dijkstraNode(d); newNode->set_next(start); start=newNode;};
        bool checkempty(void) {return start->checkempty();};
        int head(void) {if(!checkempty()) return start->get_data();};
        dijkstraList *remain(void) {dijkstraList *l=new dijkstraList(start->get_next()); return (l);};
        dijkstraNode *dijkstraList_getstart() {return start;};
        dijkstraNode *find_dijkstraNode(int n){ 
			dijkstraNode *dNode=start;	
				while(!dNode->checkempty()){
					if(dNode->get_data()==n)
						return dNode; //Devuelve el nodo de Dijkstra en caso de que se encuentre
					dNode = dNode->get_next();
				}
			return 0; //Devuelve 0 si el nodo de Dijkstra no esta
		};
        dijkstraNode *find_vmin() {
			dijkstraNode *v = start;
			dijkstraNode *v_min;
			int min=INF;
			while (!v->checkempty()){ //Mientras el nodo no sea vacio
				if(!v->get_seen()){ //Si el nodo no fue visto
					if(min > v->get_span()){ //En la primera iteracion siempre pasa
						min=v->get_span(); //Asigna la distancia minima
						v_min=v; //Se intercambia el nodo
					}
				}
				v = v->get_next(); //Continua el ciclo
			}
			return v_min; //Devuelve el nodo con distancia minima
		};
};

class streetNode{
    protected: 
        Edge *edge;
        streetNode *next;
    public:
        streetNode() {next=NULL;}; //Nodo vacio
        streetNode(Edge *a) {edge=a; next=NULL;}; //Construyo arista en el nodo
        void set_edge(Edge *a) {edge=a; };
        void set_next(streetNode *n) {next=n; };
        Edge *get_edge() {return edge; };
        streetNode *get_next() {return next; };
        bool checkempty() {return next==NULL;}
};

/* Lista de nodos que contienen aristas como dato */
class streetList{
    protected: 
		streetNode *start;
    public:
        streetList() {start=new streetNode();};
        streetList(streetNode *n) {start=n;};
        void del(void) {streetNode *aux; aux=start; start=start->get_next(); delete aux;};
        void add(Edge *d) {streetNode *newNode=new streetNode(d); newNode->set_next(start); start=newNode;};
        bool checkempty(void) {return start->checkempty();};
        streetNode *streetList_getstart() {return start;};
        Edge *head(void) {if(!checkempty()) return start->get_edge();};
        streetList *remain(void) {streetList *l=new streetList(start->get_next()); return (l);};
        void _swapdata(streetNode *_high, streetNode *_low) {Edge *aux = _low->get_edge(); _low->set_edge(_high->get_edge()); _high->set_edge(aux);};
};

/* Estructura Stack, se usa para dar el orden de los autos en los semaforos */
class Stack:public streetList{
    public:
        Stack(){streetList();};
        void _stack(Edge *x){add(x);};
        Edge *top(void){return head();};
        void _unstack(void){del();};
        bool _checkempty(){return checkempty();};
};
	
/* Estuctura correspondiente a los autos */
class streetCars{
	protected:
		int ID; //ID del auto
		int type; //Comun o especial
		int startpos; //Posicion inicial en el grafo
		int endpos; //Destino
		int pos; //Indica a que vertice va la arista
		intQueue *_path; //Cola que almacena el camino
		
	public:
		streetCars(int num, int t, int s, int e) {ID=num; type=t; startpos=s; endpos=e; _path = new intQueue();};
		int get_ID() {return ID;};
		int get_tipo() {return type;};
		int get_startpos() {return startpos;}; 
		int get_endpos() {return endpos;};	
		intQueue *get_recorrido() {return _path;};
		int get_pos() {return pos;};
		void set_pos(int pos_aux) {pos = pos_aux;};
};

/* Estructura de nodos de autos */
class carqueueNode{
    protected: 
        streetCars *car;
        carqueueNode *next_carqueueNode;
    public:
        carqueueNode() {next_carqueueNode=NULL;}; //Nodo vacio
        carqueueNode(streetCars *m) {car=m; next_carqueueNode=NULL;}; //Nodo con auto asignado
        void set_car(streetCars *m) {car=m; };
        void set_next_carqueueNode(carqueueNode *n) {next_carqueueNode=n; };
        streetCars *get_car() {return car; };
        carqueueNode *get_next_carqueueNode() {return next_carqueueNode; };
        bool checkempty() {return next_carqueueNode==NULL;};     
};

/* Lista de autos */
class carqueueList{
    protected: 
		carqueueNode *start;
    public:
		carqueueList() {start=new carqueueNode();}; //Lista vacia
		carqueueList(carqueueNode *n) {start=n;};
		void del(void) {carqueueNode *aux; aux=start; start=start->get_next_carqueueNode(); delete aux;};
		void add(streetCars *d) {carqueueNode *newNode=new carqueueNode(d); newNode->set_next_carqueueNode(start); start=newNode;};
		bool checkempty(void) {return start->checkempty();};
		streetCars *head(void) {if(!checkempty()) return start->get_car();};
		carqueueList *remain(void) {carqueueList *l=new carqueueList(start->get_next_carqueueNode()); return (l);};
		carqueueNode *get_start(void){return start;}
		void deletecar(int ID_movil){
			carqueueNode *aux = start;
			
			if(aux->get_car()->get_ID() == ID_movil) //Se elimina el primero de la lista
				start = start->get_next_carqueueNode();
				
			else{ //Se elimina alguno del resto
				
				while((aux->get_next_carqueueNode()!= NULL) && (!aux->get_next_carqueueNode()->checkempty())){ //Se compara con el NULL, primero para que no tire error cuando se quito el ultimo de la lista.
					
					if(aux->get_next_carqueueNode()->get_car()->get_ID() == ID_movil)
						aux->set_next_carqueueNode(aux->get_next_carqueueNode()->get_next_carqueueNode());	
				aux = aux->get_next_carqueueNode();
				}
			}
		};
};

/* Cola de autos */
class carqueueQueue{
    private:
		int maxcars;
		int maxspace;
		carqueueList *l;
        carqueueNode *startq;
        void update_start(carqueueList *l,carqueueNode *p) {if (l->checkempty()) startq=p; else this->update_start(l->remain(),l->get_start());};
        void dounqueue(carqueueNode *p,carqueueNode *s){
			if (p->get_next_carqueueNode()==NULL){
				if (s!=NULL)
					s->set_next_carqueueNode(NULL);
				delete(p);
			}
			else
				this->dounqueue(p->get_next_carqueueNode(),p);
		};
    public:
		carqueueQueue(int n, int type){l=new carqueueList(); maxspace=3*n*type; maxcars = 0; update_start(l,NULL);};
		~carqueueQueue(void) {delete(l);};
		streetCars *get_start() {if (!emptyqueue()) return startq->get_car();};
		bool check_space() {return maxcars < maxspace;};
		int get_maxcars() {return maxcars;};
		int emptyqueue() { return l->checkempty();};
		void _queue(streetCars *a){
			if((a->get_tipo() == 0) || (this->emptyqueue())) //En la cola vacia se agregan los autos indistintamente
				l->add(a);
			else{  //Aca se agregan al comienzo de la cola los autos prioritarios
				carqueueNode *n =new carqueueNode(a);
				n->set_next_carqueueNode(startq->get_next_carqueueNode());
				startq->set_next_carqueueNode(n);
				startq = n;
				update_start(l,NULL);
			}
			if (startq==NULL)
				update_start(l,startq);
			maxcars++; //Aumenta en uno la cantidad de autos
		};
		void _unqueue(){
			if (!emptyqueue()){
				dounqueue(l->get_start(),NULL);
				update_start(l,NULL);
			}
			maxcars--; 
		};
};

/* Estructura arista, representa las calles, dentro de los nodos se inicializa la cola de autos asociadas y los vertices iniciales y finales */
class Edge{	
	protected:
		int	n;
		int type;
		carqueueQueue *q;
		Vertex *startpos;
		Vertex *endpos;
		Edge *next_arista;
	public:
		Edge() {next_arista=NULL;};
		Edge(int num, int t, carqueueQueue *c, Vertex *o, Vertex *d) {n=num; type=t; q=c; startpos=o; endpos=d; next_arista=NULL;};
		int get_weight() {return (q->get_maxcars()/n)+1;};
		carqueueQueue *get_carqueueQueue() {return q;};
		Vertex *get_startpos() {return startpos;};
		Vertex *get_endpos() {return endpos;};
		Edge *get_next_edge() {return next_arista;};
		void set_next_edge(Edge *a) {next_arista=a;};
		bool is_empty() {return next_arista==NULL;};
		int get_edgetype() {return type;};
};

/* Estructura vertice, representa las esquinas, dentro de los nodos contiene las aristas */
class Vertex{
	protected:
			int vertexID;
			Edge *edge;
			Vertex *next_vertex;
	public:
			Vertex() {edge=new Edge(); next_vertex=NULL;};
			Vertex(int n) {vertexID=n; edge=new Edge(); next_vertex=NULL;};
			void set_next_vertex(Vertex *n) {next_vertex=n;};
			int get_vertextID() {return vertexID;};
			Vertex *get_next_vertex() {return next_vertex;};
			bool is_empty() {return next_vertex==NULL;};
			void add_edge(int n, int type, carqueueQueue *c, Vertex *startpos, Vertex *endpos) {Edge *a=new Edge(n, type, c, startpos, endpos); a->set_next_edge(edge); edge=a;};
			Edge *get_edge() {return edge;};
};
			
/* Estructura del grafo, es una lista que contiene los vertices */
class Graph{
	protected:
			int maxvertex;
			Vertex *graphVertex;
	public:
			Graph() {graphVertex=new Vertex(); maxvertex=0;};
			Graph(Vertex *v) {graphVertex=v;};
			Vertex *get_graphStart() {return graphVertex;};
			void add_vertex(int n) {Vertex *v=new Vertex(n);	v->set_next_vertex(graphVertex); graphVertex=v;};
			Graph *remain() {Graph *g=new Graph(graphVertex->get_next_vertex()); return (g);};
			bool is_empty(void) {return graphVertex->is_empty();};
			void add_edge(Vertex *startpos, Vertex *endpos, int n, int type){ //Agrego una calle, compuesta de 1 cola de autos con 1 solo sentido
				carqueueQueue *c = new carqueueQueue(n, type); 
				startpos->add_edge(n,type, c, startpos, endpos);};	
			void add_ave(Vertex *startpos, Vertex *endpos, int n, int type){ //Agrego una avenida, compuesta de 2 colas de autos con sentidos opuestos
				carqueueQueue *c1 = new carqueueQueue(n,type); 
				carqueueQueue *c2 = new carqueueQueue(n,type);
				startpos->add_edge(n,type,c1,startpos,endpos);
				endpos->add_edge(n,type,c2,endpos,startpos);
			};
};